#ifndef xpack_gc_ref
#define xpack_gc_ref
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::gc_ref::inc
#include"adapter/random_access.hpp"
#include"concurrency/lock/atom_load.hpp"
#include"concurrency/lock/atom_store.hpp"
#include"concurrency/lock/atom_swap.hpp"
#include"configure/switch.hpp"
#include"define/base_type.hpp"
#include"dumb/dummy_type.hpp"
#include"dumb/init_by.hpp"
#include"gc/self_management.hpp"
#include"gc/private/gc_background.hpp"
#include"gc/private/gc_make_guide.hpp"
#include"gc/private/gc_token.hpp"
#include"gc/private/gc_tuple.hpp"
#include"instruction/index_of_last_set.hpp"
#include"interface/can_callback.hpp"
#include"macro/xdebug.hpp"
#include"macro/xdefer.hpp"
#include"macro/xexport.hpp"
#include"macro/xmaybe_unused.hpp"
#include"macro/xmodify.hpp"
#include"macro/xstruct.hpp"
#include"macro/xnew.hpp"
#include"macro/xis_nullptr.hpp"
#include"meta/has_cast.hpp"
#include"meta/is_same.hpp"
#include"meta_seq/tin.hpp"
#include"utils/init_item_recursively.hpp"
#include"utils/memory.hpp"
#pragma pop_macro("xuser")

namespace mixc::gc_ref{
    using namespace inc;

    // 代替 nullptr 作为空对象
    inline uxx                  g_empty_mem[32];
    inline voidp                g_empty_mem_ptr = g_empty_mem;

    // 当前[潜质类型]的出度入度差
    // 如果该[潜质类型]可以通过子节点再次回到自身且 degree_dvalue 为 0 则表示可以进行[内析构]
    inline uxx                  g_degree_dvalue;

    // gc 遍历时的根节点
    inline voidp                g_root;

    template<
        class final_t, // make_guide<final_t> 需要使用 final_t 作为路由起点
        class item_t, 
        class attribute_t, 
        bool  is_array_v, 
        bool  is_binary_aligned_alloc_v
    >
    xstruct(
        xtmpl(meta, final_t, item_t, attribute_t, is_array_v, is_binary_aligned_alloc_v),
        xpubb(self_management),
        xasso(attribute_t),
        xasso(item_t)
    )
    protected:
        template<bool need_gc_v>
        static auto configure(){
            if constexpr (is_array_v){
                return inc::gc_token_plus<need_gc_v>{};
            }
            else{
                return inc::gc_token<need_gc_v>{};
            }
        }

        using converted_item_t              = item_t;

        template<bool need_gc_v>
        using token_mix_t                   = inc::gc_token_mix<item_t, attribute_t, decltype(configure<need_gc_v>())>;

        template<bool need_gc_v>
        using token_mixp_t                  = token_mix_t<need_gc_v> *;

        template<bool need_gc_v>
        using clear_token_t                 = typename token_mix_t<need_gc_v>::clear_type;

        static constexpr bool has_attribute = not is_same<inc::dummy_type, attribute_t>;
        static constexpr bool has_array     = not is_same<inc::dummy_type, item_t>;

        static voidp null(){
            return g_empty_mem_ptr;
        }

        static constexpr bool is_requires_gc(){
            return decltype(gc_make_guide<final_t>())::length != 0;
        }

        template<class guide_t>
        uxx routing() {
            using gc_tuplep         = inc::gc_tuple<attribute_t> *;
            using guide             = decltype(gc_make_guide<final_t>());
            constexpr bool need_gc  = guide::length != 0;
            auto ptr                = token_mixp_t<need_gc>(xthe.m_mem);
            auto can_arrive_root    = uxx(false);

            // 无法通向 g_root
            if (ptr == the_t::null()){
                return false;
            }

            xdebug(im_gc_meta_routing, ptr, xtypeid(attribute_t).name, ptr->owners(), ptr->visited(), xthe.length());

            // 我们把经过的节点存下来
            // 如果是首次经过就让它遍历成员节点
            // 如果该节点可以通往 g_root，那么曾经拜访过该节点的附和节点也可以通往根节点
            // 实际过程如下：
            // g_root --> 此节点 --> 附和节点 -> 此节点
            //             |
            //             +-----> 其他节点 -> g_root
            // 在此时附和节点不能确定此节点是否还存在可以通往 g_root 的路径，所以指示暂时的让此节点的 visited 访问计数器加一
            // 而计数汇总的工作则是交给此节点来完成
            if (ptr->is_visited()){
                if (ptr->can_arrive_root()){
                    xdebug(im_gc_meta_routing, "can_arrive_root");

                    // 这里必须设置 g_degree_dvalue -= 1 而不是 visited += 1
                    // 因为后续可能不一定会有关于该节点的 owners - visited
                    g_degree_dvalue-= 1;
                    return true;
                }
                else{
                    xmaybe_unused
                    uxx visited     = ptr->new_visited();
                    xdebug(im_gc_meta_routing, visited);
                    return false;
                }
            }

            // 从非根节点开始计算
            if (ptr == g_root){
                ptr->visit_root();
                ptr->can_arrive_root(true);
            }
            else {
                ptr->new_visited();
            }

            xdebug(im_gc_meta_routing, ptr, "set to gc_map");

            // 如果数组元素 item_t 属于 guide_t 类型集合，那么就遍历数组元素
            if constexpr (tin<guide_t, item_t>){
                auto length         = xthe.length();
                can_arrive_root    |= gc_tuple<void>::template routing<guide_t>(xthe, length);
            }

            // 如果 attribute_t 属于 guide_t 类型集合，就遍历该对象的字段
            if constexpr (tin<guide_t, attribute_t>){
                attribute_t * attr  = ptr; // 里氏转换
                can_arrive_root    |= gc_tuplep(attr)->template routing<guide_t>();
            }

            if (can_arrive_root){
                g_degree_dvalue    += ptr->owners() - ptr->visited();
                ptr->can_arrive_root(true);
            }
            return can_arrive_root;
        }

        template<class guide_t>
        bool can_release(){
            g_root                  = m_mem;
            g_degree_dvalue         = 0;

            // 只有可以再次回到根节点 g_degree_dvalue 的值才有意义
            if (not xthe.template routing<guide_t>()){
                return false;
            }
            return g_degree_dvalue == 0;
        }

    public:
        template<class, bool is_requires_gc_v = false>
        struct __fields : clear_token_t<is_requires_gc_v>{
        private:
            xpubgetx(length, uxx){
                xr{ 
                    using the_t = token_mix_t<is_requires_gc()>;
                    return xthe.length();
                }
            };
        };

        template<bool is_requires_gc_v>
        using gc_fields = clear_token_t<is_requires_gc_v>;

        template<bool is_requires_gc_v>
        using gc_fields_for_array = __fields<the_t, is_requires_gc_v>;

    public:
        // 忽略原子操作
        meta(decltype(nullptr)) : m_mem(the_t::null()){}

        meta() {
            // 保证对其他 cpu 缓存可以见性
            inc::atom_store(xmodify(m_mem), the_t::null());
        }

        meta(the_t & object){
            using guide             = decltype(gc_make_guide<final_t>());
            constexpr bool need_gc  = guide::length != 0;
            inc::atom_store(xmodify(m_mem), object.m_mem);
            token_mixp_t<need_gc>(m_mem)->owners_increase();
        }

        meta(the_t && object){
            auto temp               = inc::atom_swap(xmodify(object.m_mem), the_t::null());
            inc::atom_store(xmodify(m_mem), temp);
        }
    protected:
        // 对外隐藏析构函数
        ~meta(){
            xthe                    = nullptr;
        }

        using item_initial_invoke   = icallback<void(converted_item_t * item_ptr)>;
        using item_initial_invokex  = icallback<void(uxx i, converted_item_t * item_ptr)>;

        template<class initial_invoke_t, class ... args_t>
        void init(::length length, init_by<args_t...> const & init_attr, initial_invoke_t const & init_ary) {
            constexpr bool need_gc  = is_requires_gc();
            auto mem                = the_t::alloc(length, init_attr);
            inc::atom_store(xmodify(m_mem), mem);

            for(uxx i = 0; i < length; i++) {
                if constexpr (inc::has_cast<item_initial_invoke, initial_invoke_t>){
                    init_ary(token_mixp_t<need_gc>(m_mem)->item_ptr(i));
                }
                else{
                    init_ary(i, token_mixp_t<need_gc>(m_mem)->item_ptr(i));
                }
            }
        }

        template<class ... args_t, class ... argsx_t>
        void init_one_by_one(init_by<args_t...> const & init_attr, argsx_t && ... rest){
            constexpr bool need_gc  = is_requires_gc();
            auto mem                = the_t::alloc(sizeof...(rest), init_attr);
            auto items              = token_mixp_t<need_gc>(mem)->item_ptr(0);
            inc::atom_store(xmodify(m_mem), mem);
            inc::init_item_recursively((converted_item_t *)items, xforward(rest)...);
        }

        template<class ... args_t>
        void init_ptr(init_by<args_t...> const & init) {
            auto mem                = the_t::alloc(::length(0), init);
            inc::atom_store(xmodify(m_mem), mem);
        }

    #if xuse_gc
        template<class guide_t, bool need_gc_v>
        static void release(voidp ptr){
            auto mem                = (token_mixp_t<need_gc_v>)ptr;
            auto old                = (the_t *)& mem;
            auto owners             = (mem->owners());
            auto can_release        = (false);

            xdefer{
                if (can_release == false){
                    return;
                }

                // 如果可以释放
                // 设置 thread_local 变量 l_in_release 
                // 让成员变量析构操作不再推送到 gc_thread
                *inc::l_in_release  = true;
                mem->under_release(true);
                the_t::free_with_destroy<need_gc_v>(mem);
                *inc::l_in_release  = false;
            };

            // 只要计数器为 0 就可以直接释放
            // 有些[潜质类型]可能不存在环，但是此时计数器为 0
            if (owners == 0){
                can_release         = true;
                return;
            }

            if constexpr (not need_gc_v){
                ; // pass
            }
            else if (old->template can_release<guide_t>()){
                can_release         = true;
                return;
            }
        }
    #endif

    public:
        xis_nullptr(
            m_mem == the_t::null()
        );

        the_t & operator= (the_t & object){
            /* 当 object == nullptr 时，实际上指向的是 the_t::null()
             * 对外而言依旧与 nullptr 比较判断是否是空对象
             * the_t::null() 是一块不为 nullptr 可用的内存，只是我们不应该访问它里面的内容
             * 具体情况：
             * 对于该函数 operator=(the_t const & object)
             * 假如 object.m_mem 为空时指向的是 nullptr
             * 那么在增加计数器时我们需要额外判断它是否为 nullptr
             * 此外下列步骤在多线程环境并不安全：
             * 
             * // 前一刻不为 nullptr
             * if (object.m_mem != nullptr){
             *     // 后一刻在其他线程释放了
             *     // 由于 cache 的存在，当前 cpu 可能看不见其他 cpu 对它的改动
             *     object.m_mem->owners_increase();   
             * }
             * 
             * 所以我们用静态的空对象 null() 代替 nullptr
             * 这样我们我们可以放心的直接增加计数器并且消除了线程不一致问题
             */

            using guide             = decltype(gc_make_guide<final_t>());
            constexpr bool need_gc  = guide::length != 0;

            // 避免 debug 模式多次从内存中访问 object.m_mem
            // object.m_mem 前后可能不一致
            auto om                 = object.m_mem;

            if (om == m_mem){
                return xthe;
            }

            token_mixp_t<need_gc>(om)->owners_increase();

            // 当有多个线程对该对象赋值时，该原子操作可以保证正确性
            the_t         old       = nullptr;
            auto m                  = inc::atom_swap(xmodify(xthe.m_mem), om);

            // 把原先的 xthe.m_mem 交给 old 进行析构操作
            old.m_mem               = m;
            return xthe;
        }

        the_t & operator=(the_t && object){
            // 先夺取 object.m_mem
            the_t         old       = nullptr;
            auto m                  = inc::atom_swap(xmodify(object.m_mem), the_t::null());

            // 即使其他线程也想与 xthe.m_mem 交换
            // 后交换的线程会把先交换的内容挤出来放到 m 中
            // 由 old 析构
            m                       = inc::atom_swap(xmodify(xthe.m_mem), m);
            old.m_mem               = m;
            return xthe;
        }

        the_t & operator=(decltype(nullptr)){
            using thep              = the_t *;
            using guide             = decltype(gc_make_guide<final_t>());
            constexpr bool need_gc  = guide::length != 0;
            bool           ready    = false;
            auto           mem      = the_t::null();
            the_t       *  old;
            uxx            owners;

            if (mem = atom_swap(xmodify(m_mem), mem); mem == the_t::null()) {
                return xthe;
            }
            else{
                old                 = thep(xmodify(mem));
            }

            auto ptr                = token_mixp_t<need_gc>(mem);
            auto in_release         = false;

            if (ptr->under_release()) {
                return xthe;
            }

        #if xuse_gc
            // l_in_release 是一个 thread_local 变量
            // 非 gc_thread 线程 l_in_release 永远是 false
            // 前台[外析构]的剩余步骤会推送到 gc_thread 后台线程执行
            // 后台 gc_thread 线程执行[内析构]前会将 l_in_release 置 true
            // 表示[内析构]直接执行而不推送到自身的 gc_que 队列中
            // 这么做保证了释放的顺序，同时避免了 gc_que 存满时的死锁
            // 
            // 注意：
            // 这里非[潜质类型]不再使用 gc 管理，而是自行析构
            in_release              = *inc::l_in_release;

            if constexpr (need_gc) if (not in_release){
                inc::gc_push(ptr, & the_t::release<guide, need_gc>);
                return xthe;
            }
        #else
            // 当前 gc 要求 routing 操作由单线程完成，暂时不允许多个线程同时 routing
            // 所以对于[潜质类型]不允许使用关闭 gc 的此模块
            static_assert(not need_gc, "not support gc");
        #endif

            // 后续代码 return 时执行
            xdefer{
                if (not ready) {
                    return;
                }

                // 如果是在 gc 中，就走 free_with_destroy 逻辑，这样可以将内存释放操作交给其他线程完成
                // 而不用占用 gc 的宝贵时间
                // 注意：
                // 如果是 gc 中筛选已经无有效引用的对象，可以析构，但需要推迟释放内存（等到本轮 gc 结束）
                // 由于 [内部引用计数步骤] 会改变引用计数器，假如判定当前对象无有效引用，我们释放了该对象指向的内存，
                // 而 gc 队列中可能还存在和当前对象相同指向的任务，那么在队列中取出 A 任务时将会对内存非法访问
                // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                if (ptr->under_release(true); in_release){
                    the_t::free_with_destroy<need_gc>(ptr);
                }
                else{
                    the_t::free_with_destroy_directly<need_gc>(ptr);
                }
            };

            // 对于[平凡类型]只要计数器为 0 就可以[内析构]
            if constexpr (not need_gc){
                owners              = ptr->owners_decrease();
                ready               = owners == 0;
                return xthe;
            }

            // 如果 gc 经过了该节点，且它可以抵达根节点
            if (ready = ptr->can_arrive_root(); ready) {
                return xthe;
            }

            // 已访问但不可达
            if (ptr->is_visited()){
                return xthe;
            }

            // [内部引用计数步骤]
            // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            // 此节点可能不属于当前[类型环]
            // 遍历子节点，如果可以释放就执行[内析构]操作
            else {
                owners              = ptr->owners_decrease();
                ready               = owners == 0 or old->template can_release<guide>();
                return xthe;
            }
        }

        bool operator == (the_t const & object) const {
            return m_mem == object.m_mem;
        }

        bool operator != (the_t const & object) const {
            return m_mem != object.m_mem;
        }

        void swap(the_t * object) {
            object->m_mem = inc::atom_swap(& m_mem, object->m_mem);
        }

    protected:
        operator item_t * () const {
            constexpr bool need_gc  = is_requires_gc();
            return token_mixp_t<need_gc>(m_mem)->item_ptr(0);
        }

        auto operator->() const {
            constexpr bool need_gc  = is_requires_gc();

            if constexpr(is_array_v){
                return (gc_fields_for_array<need_gc> *)m_mem;
            }
            else{
                return (gc_fields<need_gc> *)m_mem;
            }
        }

        uxx length() const {
            constexpr bool need_gc  = is_requires_gc();
            return token_mixp_t<need_gc>(m_mem)->this_length();
        }

        uxx capacity() const {
            constexpr bool need_gc  = is_requires_gc();
            return the_t::real(token_mixp_t<need_gc>(m_mem)->this_length());
        }
    private:
        mutable voidp m_mem;

        static uxx real(uxx length) {
            if constexpr (is_binary_aligned_alloc_v){
                // length       capacity
                // 0        ->  1 
                // 1        ->  2
                // 2        ->  4
                // 3        ->  4
                // 4        ->  8
                // 5        ->  8
                // 6        ->  8
                // ...
                length    = uxx(1) << (index_of_last_set(length) + 1);
            }
            return length;
        }

        static inc::memory::size size(uxx length) {
            constexpr bool need_gc  = is_requires_gc();

            if constexpr (has_array){
                return inc::memory::size(
                    sizeof(token_mix_t<need_gc>) + length * sizeof(item_t)
                );
            }
            else{
                return inc::memory::size(
                    sizeof(token_mix_t<need_gc>)
                );
            }
        }

        template<class ... args_t>
        static voidp alloc(uxx length, init_by<args_t...> const & init) {
            // 这里只初始化不带属性的部分（引用计数器（*必选）、数组长度（*可选））
            constexpr bool need_gc  = is_requires_gc();

            auto real_length    = (the_t::real(length));
            auto mem            = inc::memory::alloc_with_initial<typename token_mix_t<need_gc>::base_t>(
                the_t::size(real_length), length
            );

            // 再根据实际情况初始化属性部分
            if constexpr (has_attribute){
                init.make(token_mixp_t<need_gc>(mem)->attribute_ptr());
            }
            return mem;
        }

        template<bool need_gc_v>
        static void free_with_destroy(token_mixp_t<need_gc_v> mem) {
        #if xuse_gc
            // 先析构
            mem->~token_mix_t<need_gc_v>();

            // 添加到释放列表，在完成一轮 gc 后再释放
            // 避免在对下一个和 m_mem 指向相同元素 gc 的时候，访问了释放的内存
            auto length         = the_t::real(mem->this_length());
            auto bytes          = the_t::size(length);
            auto & new_node     = free_nodep(mem)[0];
            new_node->prev      = g_free_list;
            new_node->bytes     = bytes;
            g_free_list         = xmodify(new_node);
        #else
            free_with_destroy_directly<need_gc_v>(mem);
        #endif
        }

        template<bool need_gc_v>
        static void free_with_destroy_directly(token_mixp_t<need_gc_v> mem) {
            // 先析构
            mem->~token_mix_t<need_gc_v>();

            // 添加到释放列表，在完成一轮 gc 后再释放
            // 避免在对下一个和 m_mem 指向相同元素 gc 的时候，访问了释放的内存
            auto length         = the_t::real(mem->this_length());
            auto bytes          = the_t::size(length);
            inc::memory::free(mem, bytes);
        }
    $

    #define xgen(name)                                          \
        name()                              = default;          \
        name(the_t &)                       = default;          \
        name(the_t &&)                      = default;          \
        the_t & operator=(the_t &)          = default;          \
        the_t & operator=(the_t &&)         = default;          \

    template<class final_t, class attribute_t>
    xstruct(
        xtmpl(ref_ptr, final_t, attribute_t),
        xpubb(meta<final_t, inc::dummy_type, attribute_t, false, false>)
    )
        using base_t = meta<final_t, inc::dummy_type, attribute_t, false, false>;

        xgen(ref_ptr)

        template<class ... args_t>
        requires(can_init<attribute_t, init_by<args_t...>> == true)
        ref_ptr(init_by<args_t...> const & init){
            base_t::init_ptr(init);
        }
    $

    template<
        class final_t,
        class item_t, 
        class attribute_t, 
        bool  is_binary_aligned_alloc_v
    >
    xstruct(
        xtmpl(ref_array, final_t, item_t, attribute_t, is_binary_aligned_alloc_v),
        xpubb(inc::random_access<final_t, item_t>),
        xpubb(meta<final_t, item_t, attribute_t, true, is_binary_aligned_alloc_v>)
    )
    public:
        using base_t = meta<final_t, item_t, attribute_t, true, is_binary_aligned_alloc_v>;
        using base_t::operator->;
        using typename base_t::item_initial_invoke;
        using typename base_t::item_initial_invokex;
    
        template<class invoke_t>
        static constexpr bool is_match = 
            has_cast<item_initial_invoke, invoke_t> or 
            has_cast<item_initial_invokex, invoke_t>;
    public:
        xgen(ref_array)

        template<class initial_invoke_t, class ... args_t>
        requires(
            (is_match<initial_invoke_t>) and
            (can_init<attribute_t, init_by<args_t...>>)
        )
        ref_array(::length length, init_by<args_t...> const & init_attr, initial_invoke_t const & init_ary){
            base_t::init(length, init_attr, init_ary);
        }

        template<class ... args_t, class first_t, class ... argsx_t>
        requires(
            (has_cast<item_t, first_t> and ... and has_cast<item_t, argsx_t>) and
            (can_init<attribute_t, init_by<args_t...>>)
        )
        ref_array(init_by<args_t...> const & init_attr, first_t && first, argsx_t && ... rest){
            base_t::init_one_by_one(init_attr, xforward(first), xforward(rest)...);
        }

    private:
        friend inc::random_access<final_t, item_t>;

        item_t & random_get(uxx index) const {
            return (xthe.operator item_t * ())[index];
        }
    $

    template<class final_t, class item_t, bool is_binary_aligned_alloc_v>
    xstruct(
        xspec(ref_array, final_t, item_t, inc::dummy_type, is_binary_aligned_alloc_v),
        xpubb(inc::random_access<final_t, item_t>),
        xpubb(meta<final_t, item_t, inc::dummy_type, true, is_binary_aligned_alloc_v>)
    )
        using base_t = meta<final_t, item_t, inc::dummy_type, true, is_binary_aligned_alloc_v>;
        using base_t::operator->;
        using typename base_t::item_initial_invoke;
        using typename base_t::item_initial_invokex;
    public:
        xgen(ref_array)

        template<class initial_invoke_t, class ... args_t>
        requires(
            has_cast<item_initial_invoke , initial_invoke_t> or 
            has_cast<item_initial_invokex, initial_invoke_t>
        )
        ref_array(::length length, initial_invoke_t const & init_ary){
            base_t::init(length, default_init_by, init_ary);
        }

        template<class first_t, class ... args_t>
        requires(has_cast<item_t, first_t> and ... and has_cast<item_t, args_t>)
        ref_array(first_t && first, args_t && ... rest){
            base_t::init_one_by_one(default_init_by, xforward(first), xforward(rest)...);
        }

    private:
        friend inc::random_access<final_t, item_t>;

        item_t & random_get(uxx index) const {
            return (xthe.operator item_t * ())[index];
        }
    $

    #undef  xgen
}

namespace mixc::gc_ref::origin{
    using inc::init_by;
    using mixc::gc_ref::ref_ptr;
    using mixc::gc_ref::ref_array;
}

#endif

xexport_space(mixc::gc_ref::origin)